package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 93. 复原 IP 地址 https://leetcode.cn/problems/restore-ip-addresses/
 * 题目简述：有效IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0）组成，整数之间用'.'分隔。给定一个只包含数字的字符串s，用以表示一个IP地址，返回所有可能的有效IP地址
 */
public class RestoreIpAddresses {

    public static void main(String[] args) {
        new RestoreIpAddresses().restoreIpAddresses("25525511135");
    }

    /**
     * 思路：回溯算法。关键点在于每一步的选择列表为以begin开头切子串的方式[begin, i]，尾标i范围[begin,begin+2]
     * 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：s中以下标begin开头的子串）
     * 回溯递归函数体：1.若剩余字符串的长度超过最大所需长度则直接return，否则若path长度已达到要求，说明已切完，则path加入结果集然后return
     *              2.遍历当前选择列表：若选择切出的子串[begin,i]已经不符合ip规则，则选择列表中后续子串肯定也不符合，直接return，否则将子串加入路径，
     *                  然后递归下一步选择列表[i+1, i+3]，完毕后撤销上一步选择，继续遍历同层其他选择。
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        Deque<String> path = new ArrayDeque<>();
        backTracking(result, path, s, 0);
        return result;
    }

    public void backTracking(List<String> result, Deque<String> path, String s, int begin) {
        //若剩余字符串的长度超过最大所需长度 则直接return
        if (s.length()-begin > 3*(4- path.size())) return;
        else if (path.size() == 4) {//否则若path长度已达到要求，则添加结果
            result.add(String.join(".", path));
            return;
        }
        //路径选择列表：begin开头的长度小于等于3的子串
        for(int i=begin;i < s.length() && i <= begin+2;i++) {
            String subStr = s.substring(begin, i+1);
//            if(!subStr.matches("^(?:[0-9]|[1-9][0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5])$"))
            //可行性剪枝：若当前子串已经不符合ip规则，则选择列表中后续子串肯定也不符合，直接return
            if ((subStr.startsWith("0") && subStr.length() > 1) || Integer.parseInt(subStr) > 255)
                return;
            path.add(subStr);
            backTracking(result, path, s, i+1);
            path.removeLast();
        }
    }
}
